// https://www.lintcode.com/problem/kth-smallest-element-in-a-sorted-matrix/my-submissions

// If k << n^2, what's the best algorithm?
// How about k ~ n^2?

class Node {
public:
    int x;
    int y;
    int val;
    Node (int x, int y, int val)
    {
        this->x = x;
        this->y = y;
        this->val = val;
    }
    bool operator < (const Node & n) const
    {
        return this->val > n.val;
    }
};

struct Compare {
    bool operator () (Node &a, Node &b) {
        return a.val > b.val;
    }
};

class Solution {
public:
    /**
     * @param matrix: List[List[int]]
     * @param k: a integer
     * @return: return a integer
     */
    
    // 法一：堆/优先队列
    // 加右边和下面的，是比当前大的。
    // 注意避免重复。
    // 删1个加最多两个，k次，堆大小为k
    // klogk
    int kthSmallest(vector<vector<int>> &matrix, int k) {
        // priority_queue<Node, vector<Node>, greater<Node>> q; //最小堆 直接这样报错，需要自己定义compare结构体；或者重载运算符时候反过来
        // https://www.cnblogs.com/Deribs4/p/8661931.html
        // priority_queue<Node, vector<Node>, Compare> q;
        priority_queue<Node> q;
        int n = matrix.size();
        int m = matrix[0].size();
        q.push(Node(0, 0, matrix[0][0]));
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        visited[0][0] = true;
        int dx[2] = {0, 1};
        int dy[2] = {1, 0};
        for (int i = 0; i < k - 1; ++i)
        {
            Node tmp = q.top();
            q.pop();
            for (int i = 0; i < 2; ++i)
            {
                int newX = tmp.x + dx[i];
                int newY = tmp.y + dy[i];
                if (newX < n && newY < m && !visited[newX][newY])
                {
                    q.push(Node(newX, newY, matrix[newX][newY]));
                    visited[newX][newY] = true;
                }
            }
        }
        return q.top().val;
    }
    
//     // 法二：二分法
// // 区间二分，类似的题目有kth smallest prime fraction
// // 基本原理是以matrix最小值和最大值为初始区间[l_init, r_init]。
// // 每次二分可以通过查找矩阵得出有多少个数在[l_init, mid]之间。
// // 如果个数小于k把mid调大，反之就把mid调小。
//     int kthSmallest(vector<vector<int>> &matrix, int k) {
//         if (matrix.empty())
//             return -1;
//         int n = matrix.size();
//         int m = matrix[0].size();
//         int l = matrix[0][0];
//         int r = matrix[m - 1][n - 1];
//         int cnt;
//         while (l + 1 < r)
//         {
//             int mid = (r - l) / 2 + l;
//             cnt = 0;
//             int last = -1; //需要有一个变量记录count过的数里面最大的
//             for (int i = 0; i < n; i++) {
//                 for (int j = m - 1; j >= 0; j--) {
//                     if (matrix[i][j] <= mid) {
//                         cnt += (j + 1);
//                         last = max(last, matrix[i][j]);
//                         break;
//                     }
//                 }
//             }
//             if (cnt == k)
//                 return last;
//             if (cnt < k)
//                 l = mid;
//             else
//                 r = mid;
//         }
//         if (cnt < k)
//             return r;
//         return l;
//     }


    // 优化了的区间二分
    // int kthSmallest(vector<vector<int>> &matrix, int k) {
    //     if (matrix.empty())
    //         return -1;
    //     int n = matrix.size();
    //     int m = matrix[0].size();
    //     int l = matrix[0][0];
    //     int r = matrix[m - 1][n - 1];
    //     int cnt;
    //     while (l + 1 < r)
    //     {
    //         int mid = (r - l) / 2 + l;
    //         cnt = 0;
    //         int last = -1;
    //         // for (int i = 0; i < n; i++) {
    //         //     for (int j = m - 1; j >= 0; j--) {
    //         //         if (matrix[i][j] <= mid) {
    //         //             cnt += (j + 1);
    //         //             last = max(last, matrix[i][j]);
    //         //             break;
    //         //         }
    //         //     }
    //         // }
    //         用双指针来控制遍历!!
    //         int i = 0, j = n - 1;
    //         while (i < m && j >= 0)
    //         {
    //             if (matrix[i][j] <= mid) {
    //                 cnt += (j + 1);
    //                 last = max(last, matrix[i][j]);
    //                 i++;
    //             }
    //             else
    //             {
    //                 j--;
    //             }
    //         }
    //         if (cnt == k)
    //             return last;
    //         if (cnt < k)
    //             l = mid;
    //         else
    //             r = mid;
    //     }
    //     if (cnt < k)
    //         return r;
    //     return l;
    // }
};